package 动态规划;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 最长重复数组.java
 * @Description TODO
 * @createTime 2020年11月20日 22:02:00
 * 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
 *
 *  
 *
 * 示例：
 *
 * 输入：
 * A: [1,2,3,2,1]
 * B: [3,2,1,4,7]
 * 输出：3
 * 解释：
 * 长度最长的公共子数组是 [3, 2, 1] 。
 *
 * 如果暴力解是双重for循环 大概率 优化方案是dp
 * 定义dp[i][j] 为A 以i结尾，B以j结尾的最长公共子数组。那么可以分为两类：
 * 如果A[i] == B[j], 那么有dp[i][j] = 1 + d[i-1][j-1]
 * A[i] 不等于 b[j], 则dp[i][j] = 0
 *
 *
 */
public class 最长重复数组 {
    class Solution {
        public int findLength(int[] A, int[] B) {
            int n = A.length, m = B.length;
            int[][] dp = new int[n + 1][m + 1];
            int ans = 0;
            for (int i = n - 1; i >= 0; i--) {
                for (int j = m - 1; j >= 0; j--) {
                    dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
                    ans = Math.max(ans, dp[i][j]);
                }
            }
            return ans;
        }
    }


    //一维优化空间
    class  Solution2{
        public int findLength(int[] A, int[] B) {
            int max = 0;
            int[] dp = new int[B.length + 1];
            for (int i = 1; i <= A.length; i++) {
                for (int j = B.length; j >= 1; j--) {
                    if (A[i - 1] == B[j - 1]){
                        dp[j] = dp[j - 1] + 1;
                    }

                    else{
                        dp[j] = 0;
                    }

                    max = Math.max(max, dp[j]);
                }
            }
            return max;
        }

    }

}
